%\section{Random walk lower bound (proof of Theorem~\ref{thm:rw_lower_bound})}
\section{Proof of the main theorem}\label{sec:main_theorem}
In this section, we prove Theorem~\ref{thm:rw_lower_bound}. An $\Omega(D)$ lower bound has already been shown (and is fairly straightforward) in \cite{DasSarmaNP09}; so we focus on showing the $\Omega(\sqrt{\ell D})$ lower bound. Moreover, we will prove the theorem only for the version where destination outputs source. This is because we can convert algorithms for the other two version to solve this version by adding $O(D)$ rounds. To see this, observe that once the source outputs the ID of the destination, we can take additional $O(D)$ rounds to send the ID of the source to the destination. Similarly, if nodes know their positions, the node with position $\ell$ can output the source's ID by taking additional $O(D)$ rounds to request for the source's ID. Theorem~\ref{thm:rw_lower_bound}, for the case where destination outputs source, follows from the following lemma.

\begin{lemma}
For any real $\kappa\geq 1$ and integers $\Lambda\geq 2$, and $\Gamma\geq 32\kappa^2\Lambda^{6\kappa-1}\log n$, there exists a family of networks $\cH$ such that any network $H\in \cH$ has $\Theta(\kappa\Gamma\Lambda^\kappa)$ nodes and diameter $D=\Theta(\kappa\Lambda)$, and
%a node $v$ in $H$ such that
%
any algorithm for computing the destination of a random walk of length $\ell=\Theta(\Lambda^{2\kappa-1})$ requires $\Omega(\sqrt{\ell D})$ time on some network $H\in \cH$.
\end{lemma}
\begin{proof}
We show how to compute $\PC^{r, m}$ on $G=\graph$ by reducing the problem to the problem of sampling a random walk destination in some network $H_{f_A, f_B}$, obtained by restrict the number of copies of some edges in $G$, depending on input functions $f_A$ and $f_B$. We let $\cH$ be the family of network $H_{f_A, f_B}$ over all input functions. Note that for any input functions, an algorithm on $H_{f_A, f_B}$ can be run on $G$ with the same running time since every edge in $G$ has more capacity than its counterpart in $H_{f_A, f_B}$.
%
%\danupon{Note that every node in $G$ has degree at most $2\Gamma$.}

Let $r=16\Lambda^{\kappa-1}$ and $m=\kappa^2\Lambda^{5\kappa}\log n$. Note that $2rm\leq \Gamma$.
%
For any $i\leq r$ and $j\leq m$, let %$S^{i, j}=\cP^{2(i-1)m+j}$ and $T^{i, j}=\cP^{2(i-1)m+m+j}$.
\[S^{i, j}=\cP^{2(i-1)m+j}~~~\mbox{and}~~~T^{i, j}=\cP^{2(i-1)m+m+j}\,.\]
That is, $S^{1, 1}=\cP^1$, $\ldots$, $S^{1, m}=\cP^m$, $T^{1, 1}=\cP^{m+1}$, $\ldots$, $T^{1, m}=\cP^{2m}$, $S^{2, 1}=\cP^{2m+1}$, $\ldots$, $T^{r, m}=\cP^{2rm}$.
%
%We divide the first $2rm$ paths $\cP^1, \ldots, \cP^{2rm}$ into $2r$ groups, each of $m$ paths, denoted in order by $S_1, T_1, S_2, T_2, \ldots, S_r, T_r$, i.e.,
%\[S_i=\{\cP_{2(i-1)m+1}, \ldots, \cP_{2(i-1)m+m}\} ~~~\mbox{and}~~~ T_i=\{\cP_{2(i-1)m+m+1}, \ldots, \cP_{2(i-1)m+2m}\}\,.\]
%
Let $L$ be the number of nodes in each path. Note that $L=\Theta(\kappa\Lambda^\kappa)$ by Lemma~\ref{lem:graphsize}. Denote the nodes in $S^{i, j}$ from {\em left to right} by $s^{i, j}_1, \ldots, s^{i, j}_L$. (Thus, $s^{i, j}_1=v^{2(i-1)m+j}_{-\infty}$ and $s^{i,j}_L=v^{2(i-1)m+j}_{\infty}$.) Also denote the nodes in $T^{i, j}$ from {\em right to left} by $t^{i, j}_1, \ldots, t^{i, j}_L$. (Thus, $t^{i, j}_1=v^{2(i-1)m+m+j}_{\infty}$ and $t^{i,j}_L=v^{2(i-1)m+m+j}_{-\infty}$.) Note that for any $i$ and $j$, $s^{i, j}_1$ and $t^{i, j}_L$ are adjacent to $s$ while  $s^{i, j}_L$ and $t^{i, j}_1$ are adjacent to $t$.


Now we construct $H_{f_A, f_B}$. For simplicity, we fix input functions $f_A$ and $f_B$ and denote $H_{f_A, f_B}$ simply by $H$. To get $H$ we let every edge in $G$ have one copy (thus with capacity $O(\log n)$), except the following edges.
%
For any $i\leq r$, $j\leq m$, and $x<L$, we have $(6\Gamma\ell)^{2(i-1)L+x}$ copies of edges between nodes $s^{i,j}_x$ and $s^{i,j}_{x+1}$  and $(6\Gamma\ell)^{2(i-1)L+L+x}$ copies of edges between nodes $t^{i,j}_x$ and $t^{i,j}_{x+1}$.
%
Note that these numbers of copies of edges are always the same, regardless of the input $f_A$ and $f_B$.

Additionally, we have the following numbers of edges which depend on the input functions. First, $s$ specifies the following number of edges between its neighbors. For any $i\leq r$, $j\leq m$, we have $(6\Gamma\ell)^{2(i-1)L+L}$ copies of edges between nodes $t^{i,j}_L$ and $s^{i, f_A(j)}_{1}$. These numbers of edges can be specified in one round since both $s^{i,j}_1$ and $t^{i, f_A(j)}_{L}$ are adjacent to $s$. Similarly, we have $(6\Gamma\ell)^{2(i-1)L+2L}$ copies of edges between nodes $t^{i,j}_1$ and $s^{i+1, f_B(j)}_{L}$ which can be done in one round since both nodes are adjacent to $t$. This completes the description of $H$.

Now we use any random walk algorithm to compute the destination of a walk of length $\ell=2rL-1=\Theta(\Lambda^{2\kappa-1})$ on $H$ by starting a random walk at $s^{1, f(A)}_1$. If the random walk destination is $t^{r, j}_L$ for some $j$, then node $t$ outputs the number $j$; otherwise, node $t$ outputs an arbitrary number.

Now observe the following claim. %Its proof is in Appendix~\ref{app:proof_of_claim}.

\begin{claim}\label{claim:highprob}
Node $t$ outputs $\PC^{r, m}(f_A, f_B)$ with probability at least $2/3$.
\end{claim}
\begin{proof}
Let $P^*$ be the path consisting of nodes $s^{1, f_A(1)}_1$, $\ldots$, $s^{1, f_A(1)}_L$, $t^{1, f_B(f_A(1))}_1$, $\ldots$, $t^{1, f_B(f_A(1))}_L$, $s^{1, f_A(f_B(f_A(1)))}_1$, $\ldots$, $s^{i, g^{2i-1}(f_A, f_B)}_L$, $t^{i, g^{2i}(f_A, f_B)}_1$, $\ldots$, $t^{r, g^{2r}(f_A, f_B)}_L$. We claim that the random walk will follow path $P^*$ with probability at least $2/3$. The node of distance $(2rL-1)$ from $s^{1, f_A(1)}_1$ in this path is $t^{r, g^{2r}(f_A, f_B)}_L=t^{r, \PC^{r, m}(1)}_L$ and thus the algorithm described above will output $\PC^{r, m}(1)$ with probability at least $2/3$.

To prove the above claim, consider any node $u$ in path $P^*$. Let $u'$ and $u''$ be the node before and after $u$ in $P^*$, respectively. Let $m'$ and $m''$ be the number of multiedges $(u, u')$ and $(u, u'')$, respectively. Observe that $m''\geq 6\Gamma \ell m'$. Moreover, observe that there are at most $\Gamma$ edges between $u$ and other nodes. Thus, if a random walk is at $u$, it will continue to $u''$ with probability at least $1-\frac{1}{3\ell}$. By union bound, the probability that a random walk will follow $P^*$ is at least $1-\frac{1}{3}$, as claimed.
\end{proof} 


Thus, if there is any random walk algorithm with running time $O(T)$ on all networks in $\cH$ then we can use such algorithm to solve $\PC^{r, m}$ (with error probability $1/3$) in time $O(T)$. Using the lower bound of computing solving $\PC^{r, m}$ in Lemma~\ref{lem:PC_dist_lowerbound}, the random walk computation also has a lower bound of $\Omega(\kappa\Lambda^\kappa)=\Omega(\sqrt{\ell D})$ as claimed.
%
%
%Now we consider any $\kappa$, $\Lambda\geq 2$, $K$, and $\Gamma\geq 64B d\Lambda^{7\kappa-1}$ as in the theorem statement. We will reduce the lower bound of the path chasing problem with such parameters from $\PC^{r, m, d}$ on any $G\in \graph$, with parameters $r=16\Lambda^{\kappa-1}$, $m= 4B\Lambda^{5\kappa}$ and $d=K$. To do this, we will use $\ell=r\Lambda^\kappa=16\Lambda^{2\kappa-1}$ and construct a subgraph $H$ as follows.
%
%\paragraph{Old proof without $K$.}
%
%Now, for the given parameters $D$ and $\ell$, let $\kappa$ be such that $(D/\kappa)^{2\kappa-1}=\ell/16$ (which exists since $D\leq \ell$) and $\Lambda=D/\kappa$. Note that $D=\kappa\Lambda$ and $\ell=16\Lambda^{2\kappa-1}$.
%
%
%
%
%
%
%By this choice of $m$ and $r$, conditions in the above claim hold. So, ...
%
% Recall that we consider and
%
%
%%(In other words, let $\Lambda$ be such that $\Lambda^{2D/\Lambda-1}=\ell$ OR $\kappa$ such that $(D/\kappa)^{2\kappa-1}=\ell/16 \rightarrow D^\kappa/\ell=\kappa^\kappa$) Also let $m=4B\kappa^5\Lambda^{5\kappa}$ and $r=16\Lambda^{\kappa-1}/\kappa$. (Thus, $\ell=r\kappa\Lambda^{\kappa}$. )
%
%
%$\kappa$, $\Lambda\geq 2$, $K$, and $\Gamma\geq 64B d\Lambda^{7\kappa-1}$ as in the theorem statement. We will reduce the lower bound of the path chasing problem with such parameters from $\PC^{r, m, d}$ on any $G\in \graph$, with parameters $r=16\Lambda^{\kappa-1}$, $m= 4B\Lambda^{5\kappa}$ and $d=K$. To do this, we will use $\ell=r\Lambda^\kappa=16\Lambda^{2\kappa-1}$ and construct a subgraph $H$ as follows.
%
%
%%Let $m=4B\Lambda^{5\kappa}$, $K=d$, $\ell=r\Lambda^\kappa=\Lambda^{2\kappa-1}\kappa^{-1}$ and $\Gamma=\ell md$. Let $G$ be any network in $\graph$. Let $d=K$.
\end{proof}


To prove Theorem~\ref{thm:rw_lower_bound} with the given parameters $n$, $D$ and $\ell$, we simply set $\Lambda$ and $\kappa$ so that $\kappa\Lambda=D$ and $\Lambda^{2\kappa-1}=\Theta(\ell)$. This choice of $\Lambda$ and $\kappa$ exists since $\ell\geq D$. Setting $\Gamma$ large enough so that $\Gamma\geq 32\kappa^2\Lambda^{6\kappa-1}\log n$ while $\Gamma=\Theta(n)$. (This choice of $\Gamma$ exists since $\ell\leq (n/(D^3\log n))^{1/4}$.) By applying the above lemma, Theorem~\ref{thm:rw_lower_bound} follows. \note{In this setting $n=\kappa\Gamma\Lambda^\kappa=\kappa(32\kappa^2\Lambda^{6\kappa-1}\log n)\Lambda^{\kappa}\leq 32D^3\ell^4\log n$} \danupon{Is it necessary to explain this with more detail?} 